

% 定义B树节点样式

\newpage


\section{树形DP的套路}

\begin{itemize}
	\item 确认左子树,返回什么信息,右子树返回什么信息, 
	\item `做资源整合求全集,就可以得到整棵树的信息`,不想对左数和右数的信息取进行定制化的开发,全部返回
	\item 左树,右树的信息,统统为整棵树的信息而服务
	
	\item 是否存在局部解, (左子树,右子树存在答案的可能性);
	\begin{itemize}
		\item 存在局部解,就需要,去细化左数对全集信息的影响
		\item 存在局部解,就需要去细化,右树对全集信息的影响
	\end{itemize}
	\item 开始封装 全集的信息体; 
	\item 存在局部解的情况,必须最后更新一次整体树的信息
	\begin{itemize}
		\item 在更新整数的信息值的时候,如果 待返回的全集信息 只剩一个, 直接使用三目运算符
		\item 在更新整数的信息值的时候,如果 待返回的全集信息 多于一个, 直接使用if分支进行判断
	\end{itemize}
	\item 不存在局部解,就直接 整合 左树,右树,以及整棵树的信息即可
\end{itemize}

\section{二叉树}
二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。这种结构上的限定使得二叉树成为计算机科学中研究和应用广泛的数据结构之一


%\begin{figure}
%\centering
\begin{tikzpicture}[
	%binary tree layout,node distance=1.3cm,nodes={circle,draw}
	]
	\node {1}
	child { node {2}
		child { node {3} }
		child { node {4}
			child { node {5} }
			child { node {6} }
		}
	}
	child { node {7}
		child[missing]
		child { node {8}
			child[missing]
			child { node {9} }
		}
	};
	
	\begin{scope}[xshift=5cm]
		\node {1}
		child { node {2}
			child { node {3} }
			child { node {4}
				child { node {5} }
				child { node {6} }
			}
		}
		child { node {7}
			child { node {4} }
			child { node {8}
				child[missing]
				child { node {9} }
			}
		};
	\end{scope}
\end{tikzpicture}

%\caption{二叉树示意图}
\label{fig:exampleBTree}
%\end{figure}

二叉树应该如上图所示\ref{fig:exampleBTree},左图为合法二叉树,右图为非法二叉树,树中不可交叉,不可有环


\subsection{树结构的分类}

\subsubsection{相同树}

相同树指的是两个二叉树在结构上完全相同，并且每个对应节点的值也相等。也就是说，两棵树不仅形状一样，而且在相同位置的节点存储的值也相同。在算法实现上，通常会通过深度优先搜索（DFS）或广度优先搜索（BFS）遍历两棵树，逐层比较节点的值和子树结构，以确定它们是否相同。

\begin{tikzpicture}[
	%binary tree layout,node distance=1.3cm,nodes={circle,draw}
	]
	% 跟节点
	\node {1}
	child { node {2}
		child { node {3} }
		child { node {4}
			child { node {5} }
			child { node {6} }
		}
	}
	child { node {7}
		child[missing]
		child { node {8}
			child[missing]
			child { node {9} }
		}
	};
	
	\begin{scope}[xshift=5cm]
		\node {1}
		child { node {2}
			child { node {3} }
			child { node {4}
				child { node {5} }
				child { node {6} }
			}
		}
		child { node {7}
			child[missing]
			child { node {8}
				child[missing]
				child { node {9} }
			}
		};
	\end{scope}
\end{tikzpicture}

如上图所述,这就是相同树,两颗完全一致的树
\begin{enumerate}
	\item 节点的内容一致
	\item 左子树完全一致
	\item 右子树完全一致
	
\end{enumerate}
\subsubsection{镜面树}
镜面树（Mirror Tree 或 Symmetric Tree）： 镜面树通常指的是在一棵二叉树中，如果存在这样一种变换，即对树进行水平翻转（也就是交换所有节点的左右子树）之后，得到的树与原树结构相同，但方向相反，这样的树被称为镜像对称树或对称树。镜面树关注的是树的形状特性，而不是节点的具体值。在二叉树中，一个典型的例子是满二叉树或完全二叉树，当它们的所有非叶节点都没有值或者值相同，且左右子树互为镜像时，它们可以被视为自己的镜像树。


\begin{tikzpicture}[
	level/.style={sibling distance=40mm/#1},
	level distance=1.5cm,
	%nodes={circle, draw, minimum size=1cm}
	]
	% 跟节点
	\node {1}
	child { node {2}
		child { node {3} }
		child { node {4}
			child { node {5} }
			child { node {6} }
		}
	}
	child { node {2}
		child { node {4}
			child { node {6} }
			child { node {5} }
		}
		child { node {3} }
	};
\end{tikzpicture}
% BTree
\section{B-Tree}

B树（B-tree，有时也写作B-Tree或Btree）是一种自平衡的树形数据结构，特别适用于外部存储或磁盘存储系统，因为它能够减少磁盘I/O操作次数，从而提高效率。B树的设计初衷是为了满足文件系统和数据库系统中大量数据存储和快速查找的需求。以下是B树的一些关键特性：
\begin{enumerate}
	\item 多路平衡查找树：与二叉树不同，B树的每个节点可以有多个子节点，通常子节点的数量在一个预先设定的最小值(t)到%最大值(2t-1)之间（(t \geq 2)），
	这意味着B树是一种多路平衡查找树。
	\item 自平衡：每当有新数据插入或删除时，B树都会通过分裂、合并节点或重新分配节点中的键值来自动维护树的平衡状态，确保树的高度保持在对数级别，从而保证查找、插入和删除操作的高效性。
	\item 有序结构：B树中的所有节点都按照键值的大小顺序排列，每个节点包含一个或多个键值及其关联的数据或指向下一层节点的指针。
	\item 分支因子：B树的分支因子（每个节点的子节点数）相对较大，这有助于减少树的高度，特别是在磁盘I/O密集型操作中尤为重要，因为每次I/O操作涉及的节点数更多。
	\item 搜索效率：由于B树的高度较低，对于包含大量数据的树，搜索、插入和删除操作的时间复杂度可以保持在对数级别，通%常是(O(log_{t}N))，其中(N)是树中节点的数量，(t)是分支因子。
	应用场景：B树广泛应用于数据库索引、文件系统（如Ext4、NTFS）以及其他需要高效随机访问大量数据的场景。
\end{enumerate}

在这里我们以5叉为例,那么此时的m=5，那么他的分支数为 \lceil \frac{m}{2} \rceil - 1 \leq n \leq m - 1 ,

其中n为分支树,我们以插入的节点顺序为 
C,N,G,A,H,E,K,Q,M,F,W,L,T,Z,D,P,R,X,Y,S

\textbf{插入 C,N,G,A节点时,进行排序比较}

\begin{tikzpicture}[grow=down, sloped,treenode/.style = {
		rectangle split,
		rectangle split parts=3,
		draw,
		align=center,
		rectangle split horizontal,
		text width=1.5cm,
		font=\small},
	every node/.style = {treenode},
	level 1/.style = {sibling distance=3cm, level distance=2cm},
	level 2/.style = {sibling distance=2cm, level distance=1.5cm},
	level 3/.style = {sibling distance=1.5cm, level distance=1cm},]
	\node [treenode] {}
	child {node [treenode] {}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
	}
	child {node [treenode] {}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
	}
	child {node [treenode] {}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
	}
	child {node [treenode] {}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
	}
	child {node [treenode] {}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
		child {node [treenode] {}}
	};
\end{tikzpicture}

测试

\begin{tikzpicture}[level/.style={sibling distance=5cm/#1}, level distance=1.5cm, arr/.style={
		rectangle split,
		rectangle split parts=3,
		draw,
		align=center,
		rectangle split horizontal,
		text width=1.5cm,
		font=\small
	}]
	\node[arr] {1 \nodepart{two} [1,2,3]}
	child {node[arr] {2 \nodepart{two} [4,5,6] \nodepart{three} 2 }
		child {node[arr] {3 \nodepart{two} [7,8,9]}}
		child {node[arr] {4 \nodepart{two} [10,11,12]}}
	}
	child {node[arr] {5 \nodepart{two} [13,14,15]}
		child {node[arr] {6 \nodepart{two} [16,17,18]}}
		child {node[arr] {7 \nodepart{two} [19,20,21]}}
	};
\end{tikzpicture}